package com.yiwenup.leetcode.offer;

import com.yiwenup.leetcode.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/
 **/
public class No055 {
    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：38.3 MB, 在所有 Java 提交中击败了66.65%的用户
     */
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了23.38%的用户
     * 内存消耗：38.4 MB, 在所有 Java 提交中击败了47.92%的用户
     */
    public int maxDepth2(TreeNode root) {
        if (root == null) return 0;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int size = 1;

        int deep = 0;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            size--;

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);

            if (size == 0) {
                deep++;
                size = queue.size();
            }
        }
        return deep;
    }
}
